package leetcode.greed;

import java.util.Arrays;

//[2,-3,-1,5,-4] 2
//[-8,3,-5,-3,-5,-2]
//[-2,5,0,2,-2]
public class Test1005 {

    public static void main(String[] args) {
        int[] nums = {-2,5,0,2,-2};
        int i = largestSumAfterKNegations(nums, 3);
        System.out.println(i);
    }

    public static int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int min = nums[0]>0?nums[0]:-nums[0];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                sum += nums[i];
            } else if(k>0) {
                sum += -nums[i];
                k--;
            }
            else{
                sum += nums[i];
            }
            if (nums[i] >0 && nums[i] < min){
                min = nums[i];
            }
            else if(nums[i] < 0 && -nums[i] < min){
                min = -nums[i];
            }
            else if(nums[i] == 0){
                min = 0;
            }
        }
        if (k % 2 == 0){
            return sum;
        }
        sum -= min * 2;
        return sum;
    }
}
